#include <gc/gc.h>

#include "symbol-table.h"

typedef struct _symbol_entry
{
  UChar pivot;
  struct _symbol_entry *left;
  struct _symbol_entry *right;
  union {
    void *successor;
    symbol_t symbol;
  } payload;
} symbol_entry_t;

symbol_entry_t *symbol_table;
UChar **identifier_table;
size_t identifier_table_size;
symbol_t max_symbol;

void init_symbols()
{
  max_symbol = 0;
  identifier_table_size = 512;
  identifier_table = (UChar**)GC_MALLOC(identifier_table_size * sizeof(UChar*));
  symbol_table = NULL;
}

/*
  Create a new symbol entry pivoted on *identifier.
*/

symbol_entry_t *new_entry(UChar *identifier)
{
  symbol_entry_t *symbol_entry;

  symbol_entry = GC_MALLOC(sizeof(symbol_entry_t));
  symbol_entry->pivot = *identifier;

  return symbol_entry;
}

/*
  Return the next available symbol.
*/

symbol_t new_symbol(UChar *identifier)
{

  symbol_t symbol;

  if(max_symbol >= identifier_table_size)
  {
    identifier_table_size *= 2;
    identifier_table = GC_REALLOC(identifier_table, identifier_table_size * sizeof(UChar*));
  }

  symbol = max_symbol++;
  identifier_table[symbol] = identifier;

  return symbol;
}

/*
  Takes an identifier and searches for the associated symbol.
  If no symbol is found, the next symbol is allocated to the
  identifier.
*/

symbol_t get_symbol(UChar *identifier)
{

  UChar *full_identifier = identifier;
  symbol_entry_t **parent = &symbol_table;
  symbol_entry_t *entry = 0;

  symbol_t next;

  while(1)
  {
    entry = *parent;

    if(NULL == entry)
    {
      /*
        The rest of this path is obviously empty.
        We should do a flat allocation.
      */
      UChar *identifier_head = identifier++;
      entry = new_entry(identifier_head);
      *parent = entry;
      if(0 == *identifier_head)
      {
        symbol_t symbol = new_symbol(full_identifier);
        entry->payload.symbol = symbol;
        return symbol;
      }
      else
      {
        parent = (symbol_entry_t**)&(entry->payload);
      }
    }
    else if(entry->pivot < *identifier)
    {
      parent = &(entry->left);
      //identifier++;
    }
    else if(entry->pivot > *identifier)
    {
      parent = &(entry->right);
      //identifier++;
    }
    else
    {
      if(0 == entry->pivot)
      {
        return entry->payload.symbol;
      }

      parent = (symbol_entry_t**)&(entry->payload);
      identifier++;
    }
  }

  // We should never get here :)
  assert(0);
  return 0;
}

UChar *get_identifier_string(symbol_t symbol)
{
  // No identifier is associated with a symbol this large
  if(max_symbol < symbol)
    return (UChar*)0;

  return identifier_table[symbol];
}
